package nodelist

// https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/xv02ut/
// 两个链表的交集
// 算法: 先得到两个链表的长度差值，然后让比较长的链表先走，再判断是否会有重复的节点
func getIntersectionNode(headA, headB *ListNode) *ListNode {
	if nil == headA || nil == headB {
		return nil
	}

	lenA, lenB := getListNodeLen(headA), getListNodeLen(headB)
	lenDiff := 0
	if lenA > lenB {
		lenDiff = lenA - lenB
		headA = moveListNode(headA, lenDiff)
	} else {
		lenDiff = lenB - lenA
		headB = moveListNode(headB, lenDiff)
	}

	for nil != headA {
		if headA == headB {
			return headA
		}
		headA = headA.Next
		headB = headB.Next
	}
	return nil
}

// 获取链表的长度
func getListNodeLen(head *ListNode) (len int) {
	len = 0
	if nil == head {
		return
	}
	for nil != head {
		len++
		head = head.Next
	}
	return
}

// 移动链表到指定长度之后的位置
func moveListNode(head *ListNode, step int) *ListNode {
	for step > 0 {
		step--
		head = head.Next
	}
	return head
}
